"""
难度：中等
给定两个整数 n 和 k，按照下面的规则来生成字符串：

第一行写上一个 0。
从第二行开始，每一行将上一行的 0 替换成 01，1 替换为 10。
1
2
3
4
第一行：0
第二行：01
第三行：0110
第四行：01101001
要求：输出第 n 行字符串中的第 k 个字符。
"""
class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if k % 2 == 1:
            return self.kthGrammar(n-1, (k+1) // 2)
        else:
            return abs(self.kthGrammar(n-1, k // 2) - 1)